package com.java_foundation.arithmetic;

public class InsertionSort {
    /**
     * 插入排序
     *
     * 1. 从第一个元素开始，该元素可以认为已经被排序
     * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3. 如果该元素（已排序）大于/小于新元素，将该元素移到下一位置
     * 4. 重复步骤3，直到找到已排序的元素小/大于或者等于新元素的位置
     * 5. 将新元素插入到该位置后
     * 6. 重复步骤2~5
     * @param nums  待排序数组
     */
    public void insertioSort(int[] nums){
        int len = nums.length;
        for(int i=1;i<len;i++){
            int temp = nums[i];//取出下一个元素，在已排序的元素中从后向前扫描
            for(int k=i;k>=0;k--){
                if(k>0&&nums[k-1]>temp){
                    nums[k] = nums[k-1];//该元素大于取出的temp,则temp移动到前面
                }else{
                    //将新元素插入到temp位置后
                    nums[k] = temp;
                    break;
                }
            }
        }
    }

    /**
     * 交换次数较多的实现优化
     * @param nums
     */
    public void insertSort1(int[] nums){
        int len = nums.length;
        for (int i=0;i<len-1;i++){
            for(int k=i+1;k>0;k--){
                if(nums[k-1]<=nums[k]){
                    break;
                }
                int temp = nums[k];//直接交换前后位置
                nums[k] = nums[k-1];
                nums[k-1] = temp;
            }
        }
    }
}
